<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
      "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta http-equiv="content-type" content="text/html; charset=UTF-8" />
  <title>Backtracking</title>
  <meta name="generator" content="Amaya, see http://www.w3.org/Amaya/" />
</head>

<body>
<h1>Backtracking</h1>

<p>Backtracking es una técnica de programación que permite abordar un
problema de búsqueda sobre un espacio que puede o no ser finito. Básicamente
backtracking es un método que se aprovecha de la velocidad de los ordenadores
digitales para emplear una estrategia de “fuerza bruta” <span
style="background-color:#ffff00">definir?</span>, para derivar de esta forma la
solución de problemas con restricciones. Esto es: dado un conjunto C de
elementos (dominio del problema) y un conjunto de restricciones R, la idea es
encontrar, con la ayuda de backtracking, uno o más elementos —o grupo de
elementos— que pertenezcan a C y a su vez satisfagan los elementos
restricciones de R.</p>

<p>La utilización de backtracking para abordar problemas de restricciones
tiene dos propiedades que pueden considerarse ventajosas. Con el empleo de
backtracking podemos ejecutar una búsqueda:</p>
<ul>
  <li>Completa: Al ser un estrategia estructurada y ordenada podemos asegurar
    que se recorrerán todos los posibles estados dentro del espacio de
    búsqueda pertenecientes a un problema.</li>
</ul>
<ul>
  <li>Eficiente: De nuevo gracias al orden que se aplica a la estrategia de
    búsqueda <span style="background-color:#ffff00"><span
    style="background-color:#ffa500">DEFINIR</span></span>, esta asegura no
    evaluar más de una vez un estado que ya se exploró.</li>
</ul>

<p><span style="background-color:#90ee90">// Tradar de destacar un poco más
las carasterísticas del backtracking,por ejemplo poner un título que diga
definición</span></p>

<p><span style="background-color:#ffff00">Veamos el funcionamiento y una
posible aplicación de backtracking a través de un sencillo ejemplo:</span></p>

<p></p>

<p><strong>Ejemplo</strong>: Supongamos que disponemos de los números enteros
del 0 al 20, y deseamos enumerar todos los posibles grupos de números
distintos entre sí tal que su suma sea mayor o igual que 20.</p>

<p>(podría preferirse una formulación más matemática de este ejemplo,
sujeto a discusión)</p>

<p></p>

<p>Aquí vemos que el “dominio” del problema es el conjunto de números
enteros que pertenecen al rango [0;20]. El conjunto de restricciones está
formado por 2 elementos:</p>

<p style="margin-left:2em;">Restricción 1: Los números que conforman la suma
deben ser distintos.</p>

<p style="margin-left:2em;">Restricción 2: La suma de los números debe ser
mayor o igual que el valor 20.</p>

<p></p>

<p>Luego, aplicando una estrategia de backtracking podemos crear un árbol de
búsqueda implícito (es decir se crea a medida que se recorre) que enumere
todos los estados que se derivan del dominio del problema, es decir tanto los
que son solución como los que no. Aplicando conjuntamente las restricciones a
dicho espacio generado daremos con el conjunto solución del problema.</p>

<p></p>

<p><span style="background-color:#ffff00">{ insert GRÁFICO QUE MUESTRA UN
POSIBLE RECORRIDO EN BACKTRACKING }</span></p>

<p></p>

<h2>Aplicaciones</h2>

<p>En qué tipo de problemas se puede o no aplicar backtracking (por la elevada
complejidad), hablar sobre el límite de 10<sup>6</sup> (ejemplo de las
<em>n</em> reinas). Ventajas y desventajas.</p>

<h2>Representación e implementación</h2>

<p>Usar la de la herramienta, detallando lo más posible cada método y
estructura de datos.</p>

<p><span style="background-color:#90ee90">Ver: el tema de la estructura de
datos: hacer incapie en como modelar la estructura para realizar el
backtracking. Analizar las dimensiones (por ejemplo: sudoku 2 dim, permutacion
1 dim, etc)</span></p>

<p></p>

<h2>Poda de ramas y optimizaciones <span
style="background-color:#ffff00"></span></h2>

<p>Concepto de poda y cómo afecta notablemente la complejidad del algoritmo,
proponer atenerse a la estructura de backtracking modificando solamente las
funciones a implementar, salvo algunas excepciones</p>

<p></p>

<h2>Problemas resueltos (ACM)</h2>

<h2>Problemas propuestos</h2>

<p>Algunos que hallamos resuelto nosotros, poner consejos (hints) al final del
cap. como en Programming Challenges.</p>

<p></p>

<p><span style="background-color:#ffff00">TO DO:</span></p>
<ul>
  <li>normalizar definiciones (definir de entrada los conceptos que se
    utilizarán en la jerga del backtracking y utilizarlos de manera
    consistente) <span style="background-color:#ffa500">ESTRATEGIA,
  etc.</span></li>
  <li>realizar el gráfico ejemplo</li>
  <li>Realizar investigación bibliográfica, a la vez que se deberá apuntar
    la bibliografía utilizada.</li>
</ul>
</body>
</html>
